GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Gottes Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Gottes Algorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Gottes Algorithmus</b> (englisch <i>God’s Algorithm</i>) ist ein Begriff aus Diskussionen über die optimale Lösung des <a href="Zauberw%C3%BCrfel" class="mw-redirect" title="Zauberwürfel">Zauberwürfels</a>. Die Formulierung stammt von dem englischen Gruppentheoretiker <a href="John_Horton_Conway" title="John Horton Conway">John Conway</a> oder einem seiner Kollegen in Cambridge.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Sie kann auch auf andere Probleme der <a href="Kombinatorik" title="Kombinatorik">Kombinatorik</a> und <a href="Spieltheorie" title="Spieltheorie">Spieltheorie</a> bezogen werden. Ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> wird als <i>Gottes Algorithmus</i> für ein Problem oder Puzzle bezeichnet, wenn er stets eine Lösung mit kleinstmöglichster Anzahl von Schritten oder Zügen produziert.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendungsbereich_und_Definition">Anwendungsbereich und Definition</h2></div>

<p>Der Begriff <i>Gottes Algorithmus</i> bezieht sich jeweils auf ein Problem oder Puzzle, das eine <a href="Endliche_Menge" title="Endliche Menge">endliche</a> Anzahl von „Konfigurationen“ annehmen kann, in Verbindung mit einer eher kleinen, wohldefinierten Menge an „Zügen“, die Transformationen zwischen Konfigurationen darstellen. Ein Puzzle lösen heißt, von irgendeiner willkürlichen Startkonfiguration aus eine oder mehrere bestimmte spezifische „Endkonfigurationen“ (von endlicher Anzahl) durch die Anwendung einer Sequenz von Zügen zu erreichen. Eine solche Zugsequenz entspricht einer <i>Lösung</i> des Puzzles.

</p><p>Auf einige gut bekannte Puzzle trifft die Beschreibung zu, z. B. <a href="Mechanische_Geduldspiele" title="Mechanische Geduldspiele">Mechanische Geduldspiele</a> wie den Zauberwürfel, <a href="T%C3%BCrme_von_Hanoi" title="Türme von Hanoi">Türme von Hanoi</a> und das <a href="15-Puzzle" title="15-Puzzle">15-Puzzle</a>. Auch <a href="Solit%C3%A4r_(Brettspiel)" title="Solitär (Brettspiel)">Solitaire</a> zählt dazu, ebenso viele <a href="Logical" title="Logical">Logik-Puzzle</a> wie das Problem der <a href="Missionare_und_Kannibalen" class="mw-redirect" title="Missionare und Kannibalen">Missionare und Kannibalen</a>. Ihnen gemeinsam ist die <a href="Mathematisches_Modell" title="Mathematisches Modell">mathematische Modellierbarkeit</a> als <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteter Graph</a>, wobei die Konfigurationen den Knoten („Punkten“) und die Züge den Kanten („Pfeilen“) des Graphen entsprechen. Eine lösende Zugsequenz (eine Lösung des Puzzles) entspricht dabei einem (gerichteten) Pfad im Graphen, der von einer Ausgangs- zu einer Endkonfiguration führt.

</p><p>Ein Algorithmus heißt <i>lösend</i>, wenn er zu einer willkürlichen Anfangskonfiguration als Eingabe

</p>

<ul><li>eine Lösung ausgibt, falls das Puzzle von der Anfangskonfiguration lösbar ist, und andernfalls</li>

<li>ausgibt, dass es keine Lösung gibt.</li></ul>

<p>Eine Lösung heißt <i>optimal</i>, wenn die Sequenz von Zügen so kurz wie möglich ist. Ein lösender Algorithmus für ein Puzzle wird <i>Gottes-Algorithmus</i> genannt, wenn er stets eine optimale Lösung ausgibt. <i>Gottes Zahl</i> schließlich ist definiert als die Länge der längsten Zugsequenz unter allen optimalen Lösungen für das Puzzle.

</p><p>Ein echter „Gottes-Algorithmus“ soll auch <i>praktikabel</i> sein, d. h. nicht außergewöhnlich viel Speicherplatz oder Zeit benötigen. Bei vielen Puzzles könnte man zwar mit Hilfe einer riesigen <a href="Lookup-Tabelle" title="Lookup-Tabelle">Lookup-Tabelle</a>, indiziert über alle Startkonfigurationen, schnell eine Lösung ausgeben können, aber dieses Vorgehen würde zu viel Speicherplatz erfordern.

</p><p>Anstatt nach einer vollständigen Lösung zu fragen, kann man auch nach dem besten ersten Einzelzug nach der Startkonfiguration fragen. Ein Algorithmus für einzelne Züge kann in einen Algorithmus für die Gesamtlösung transformiert werden, indem man ihn bis zur Schlusskonfiguration wiederholt. Umgekehrt kann so auch der Algorithmus für die Gesamtlösung in Algorithmen für Einzelzüge zerlegt werden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<th>Problem</th>

<th>Gottes Zahl</th>

<th>Größe des Zustandsraums</th>

<th>Verdienst / Anmerkungen</th>

<th>Jahr

</th></tr>

<tr>

<td>N-Puzzle<br>(das verallg. <a href="15-Puzzle" title="15-Puzzle">15-Puzzle</a>)</td>

<td><a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a>, vergleiche Ratner und Warmuth<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></td>

<td>1990

</td></tr>

<tr>

<td><a href="15-Puzzle" title="15-Puzzle">15-Puzzle</a></td>

<td>80<br>(durchschnittlich 52,6)</td>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {16!}{2}}=10.461.394.944.000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4754217e299fc72a27a1790994157f1d342447c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:25.768ex; height:5.343ex;" alt="{\displaystyle {\frac {16!}{2}}=10.461.394.944.000}" loading="lazy"></span></td>

<td>Korf und Schultze<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></td>

<td>2005

</td></tr>

<tr>

<td>8-Puzzle</td>

<td>31<br>(durchschnittlich 22)</td>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {9!}{2}}=181.440}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fee6deb27e573361f9b3206483344f10469de0a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.365ex; height:5.343ex;" alt="{\displaystyle {\frac {9!}{2}}=181.440}" loading="lazy"></span></td>

<td>Reinefeld<sup id="cite_ref-Reinefeld_1993_4-0" class="reference"><a href="#cite_note-Reinefeld_1993-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></td>

<td>1993

</td></tr>

<tr>

<td>3-Puzzle</td>

<td>6<br>(durchschnittlich 3)</td>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {4!}{2}}=12}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/106a928ff4beff8d5f2d94b2ca4b2344c975519d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:8.069ex; height:5.343ex;" alt="{\displaystyle {\frac {4!}{2}}=12}" loading="lazy"></span></td>

<td>Reinefeld<sup id="cite_ref-Reinefeld_1993_4-1" class="reference"><a href="#cite_note-Reinefeld_1993-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></td>

<td>1993

</td></tr>

<tr>

<td><a href="T%C3%BCrme_von_Hanoi" title="Türme von Hanoi">Türme von Hanoi</a><br>mit <i>n</i> Scheiben</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}-1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/51e4bd4ef2f9549d026cbf643a91c0d12a8c6794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.384ex; height:2.509ex;" alt="{\displaystyle 2^{n}-1}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/193abd21d79ceb2992929ab3b3a1ee97d2afb6a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 3^{n}}" loading="lazy"></span></td>

<td>siehe auch Rueda<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></td>

<td>historisch

</td></tr>

<tr>

<td><a href="Zauberw%C3%BCrfel" class="mw-redirect" title="Zauberwürfel">Zauberwürfel</a></td>

<td>20 (Viertel- und Halbdrehungen)<br> bzw. 26 (nur Vierteldrehungen;<br>Halbdrehung zählt als 2 Vierteldrehungen)</td>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {8!\cdot 3^{8}\cdot 12!\cdot 2^{12}}{3\cdot 2\cdot 2}}=}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eef902dd9190482a1646d26880cd63febe627582.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.363ex; height:5.676ex;" alt="{\displaystyle {\frac {8!\cdot 3^{8}\cdot 12!\cdot 2^{12}}{3\cdot 2\cdot 2}}=}" loading="lazy"></span><br><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 43.252.003.274.489.856.000}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 43.252.003.274.489.856.000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4cb355f10599d5d09e5d93158c98fd0a288c2f03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:27.13ex; height:2.176ex;" alt="{\displaystyle 43.252.003.274.489.856.000}" loading="lazy"></span></td>

<td>Rokicki, Davidson, Dethridge und Kociemba<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>, siehe auch <a href="Rubiks_Cube#Optimale_Lösungen" class="mw-redirect" title="Rubiks Cube">Optimale Lösungen des Zauberwürfels</a></td>

<td>2010 <br> bzw. 2014

</td></tr>

<tr>

<td><a href="Schach" title="Schach">Schach</a></td>

<td>Eine <a href="Endspieldatenbank" title="Endspieldatenbank">Endspieldatenbank</a> im <a href="Schach" title="Schach">Schach</a> findet den kürzesten Weg zum <a href="Schachmatt" title="Schachmatt">Schachmatt</a>.</td>

<td>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Orakel-Turingmaschine" title="Orakel-Turingmaschine">Orakel-Turingmaschine</a></li>

<li><a href="Methoden_zum_L%C3%B6sen_des_Zauberw%C3%BCrfels" title="Methoden zum Lösen des Zauberwürfels">Methoden zum Lösen des Zauberwürfels</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>David Joyner: <i>Adventures in Group Theory.</i> Johns Hopkins University Press (2002), ISBN 0-8018-6947-1.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Vgl. Jerry Slocum: <i>The Cube. The Ultimate Guide to the World's Bestselling Puzzle. Secrets – Stories – Solutions.</i> New York: Black Dog & Leventhal, 2009, S. 26.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">D. Ratner, M. Warmuth: <i>Finding a shortest solution for the (N X N)-extension of the 15-puzzle is intractable</i>. Journal of Symbolic Computation 10 (1990), S. 111–137</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Richard E. Korf; Peter Schultze: <a rel="nofollow" class="external text" href="http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf"><i>Large-Scale Parallel Breadth-First Search</i></a> (PDF; 104 kB). In: AAAI Conference On Artificial Intelligence. Proceedings of the 20th national conference on Artificial intelligence 3 (2005), S. 1380–1385, hier S. 1384–1385 (Fifteen Puzzle), Table 2 (States as a Function of Depth for Fifteen Puzzle).</span>

</li>

<li id="cite_note-Reinefeld_1993-4"><span class="mw-cite-backlink">↑ <sup><a href="#cite_ref-Reinefeld_1993_4-0">a</a></sup> <sup><a href="#cite_ref-Reinefeld_1993_4-1">b</a></sup></span> <span class="reference-text">Alexander Reinefeld: <a rel="nofollow" class="external text" href="https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.7500"><i>Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*.</i></a> In: Proceedings of the 13th International Joint Conference on Artificial Intelligence (1993), Chambery Savoi, France, S. 248–253.</span>

</li>

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304085917/http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc">Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> des <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><span class="dewiki-iconexternal"><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fwww.jamesdang.com%2FDocuments%2FAn%2520optimal%2520solution%2520of%2520Hanoi%2527s%2520toweri.doc">Originals</a></span> vom 4. März 2016 im <i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a></i>) <small class="archiv-bot"><span class="wp_boppel noviewer" aria-hidden="true" role="presentation"><span typeof="mw:File"><span title="i"></span></span></span> <b>Info:</b> Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.</small><span style="display:none"><a rel="nofollow" class="external text" href="http://IABotmemento.invalid/http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc">@1</a></span><span style="display:none"><a rel="nofollow" class="external text" href="http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc">@2</a></span><span style="display:none">Vorlage:Webachiv/IABot/www.jamesdang.com</span> (<a href="Microsoft_Word" title="Microsoft Word">MS Word</a>; 33 kB)</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.cube20.org/">God's Number is 20</a> (cube20.org)</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-08-17" href="https://de.wikipedia.org/wiki/?title=Gottes_Algorithmus&oldid=258928273">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>